package java学习.算法.动态规划.暴力递归与动态规划;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/19 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 凑货币问题 {

    //  有一个表示货币面值的数组arr，每种面值的货币可以使用任意多张。arr数组元素为正数，且无重复值。例如[7,3,100,50]这是四种面值的货币。

    //      问：给定一个特定金额Sum，我们用货币面值数组有多少种方法，可以凑出该面值。例如P=1000,用这是四种面值有多少种可能凑出1000
    public static int ways1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return way(arr, 0, aim);
    }

    //  remain: 当前剩余
    public static int way(int[] arr, int index, int remain) {

        if (index == arr.length) { // 此时来到最后一张货币，没有货币可以选择了
            return remain == 0 ? 1 : 0;
        }
        int res = 0; // 总种数
        //        i: 某货币的张数  arr[index]; 当前货币值
        for (int i = 0; i * arr[index] <= remain; i++) {
            res += way(arr, index + 1, remain - i * arr[index]);
        }
        return res;
    }

    public static int ways2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int n = arr.length;
        int[][] dp = new int[n + 1][aim + 1];
        for(int i = 0 ; i < dp.length; i++) {
            for(int j = 0 ; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        return wayfordp(arr, 0, aim,dp);
    }
    //    记忆化搜索
    public static int wayfordp(int[] arr, int index, int remain,int[][] dp) {


        if (dp[index][remain] != -1) {
            return dp[index][remain];
        }

        if (index == arr.length) { // 此时来到最后一张货币，没有货币可以选择了

            dp[index][remain] = remain == 0 ? 1 : 0;
            return dp[index][remain];
        }
        int res = 0; // 总种数
        //        i: 某货币的张数  arr[index]; 当前货币值
        for (int i = 0; i * arr[index] <= remain; i++) {
            res += wayfordp(arr, index + 1, remain - i * arr[index],dp);
        }
        dp[index][remain] = res;
        return res;

    }

    //    dp1 ： 此时已经与题意无关，。
    public static int waydp1(int[] arr, int remain) {
        if (arr == null || arr.length == 0 || remain < 0) {
            return 0;
        }
        int n = arr.length;
        int[][] dp = new int[n + 1][remain + 1];
        // 确定dp数组的空间、变量（影响参数）
        // 试几个例子判断是否存在重复情况    呃，已经是了
//            if (index==arr.length){ // 此时来到最后一张货币，没有货币可以选择了
//                return remain==0?1:0;
//            }
//            确定以上可知：初始值 如果 index=n, remain=0 ，则 为1.
        dp[n][0] = 1;
//      return   way(arr,0,aim);       要 返回的结果 的是： dp[0][remain]
//        已知左下角，返回 右上角，则从下往上计算，列上没要求。
        for (int index = n - 1; index >= 0; index--) {  // 第n行已有值：1
            for (int rest = 0; rest <= remain; rest++) {
                int res = 0; // 总种数
                for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
//                    直接根据记忆化搜索修改：
//                    dp[index][rest] = 该节点的下一行节点：dp[index + 1][rest - zhang * arr[index]]的 之前值都加起来。

                    res += dp[index + 1][rest - zhang * arr[index]];
                }
                dp[index][rest] = res;
            }

        }
        return dp[0][remain];
    }

    //    dp2 ：
    public static int waydp2(int[] arr, int remain) {
        if (arr == null || arr.length == 0 || remain < 0) {
            return 0;
        }
        int n = arr.length;
        int[][] dp = new int[n + 1][remain + 1];
        dp[n][0] = 1;
        for (int index = n - 1; index >= 0; index--) {  // 第n行已有值：1
            for (int rest = 0; rest <= remain; rest++) {
                dp[index][rest] = dp[index+1][rest];
                if(rest-arr[index]>=0){
                    dp[index][rest] += dp[index][rest-arr[index]];
                }

            }

        }
        return dp[0][remain];



    }
    public static void main(String[] args) {
        int[] arr = { 5, 10,50,100 };
        int sum = 1000;
        System.out.println(ways1(arr, sum));
        System.out.println(ways2(arr, sum));
        System.out.println(waydp1(arr, sum));
        System.out.println(waydp2(arr, sum));
    }
}
